package leetcode.hot100;

import leetcode.common.ListNode;

@SuppressWarnings("all")
public class _142_环形链表2 {

    // 给定一个链表，返回链表开始入环的第一个节点
    // 如果链表无环，则返回 null
    // 不允许修改给定的链表
    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;
        // 先确定快慢指针的相遇点
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            // 如果有环，那快慢指针一定会在环中的某一点相遇
            // 由于快指针每次都比慢指针多走一步，所以快指针走过的路程一定是慢指针的两倍
            if (fast == slow) {
                break;
            }
        }
        // 有可能是因为无环导致的循坏结束
        if (fast == null || fast.next == null) return null;
        // 快指针从头往后与慢指针每次走一步即可到达相遇点
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

    // 设链表中环外部分的长度为a，slow 指针进入环后，又走了 b 的距离与 fast 相遇
    // 此时，fast 指针已经走完了环的 n 圈 (n必然大于等于1)
    // fast指针走过的总距离为 a+n(b+c)+b = a+(n+1)b+nc
    // 隐藏条件：任意时刻，fast 指针走过的距离都为 slow 指针的 2 倍
    // 因此，我们有 a+(n+1)b+nc=2(a+b) ===》 a=c+(n-1)(b+c) ===> a=c
    // 从最后得出的等量关系，我们会发现：从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离
    // 因此，当发现 slow 与 fast 相遇时，我们再额外使用一个指针 ptr，起始，它指向链表头部
    // 随后，它和 slow 每次向后移动一个位置
    // 最终，它们会在入环点相遇
}
